---
id: unit8
title: 第八章  图的应用
---



8.1 图的基本概念

图中的边均为有向边的图称为有向图。如果图中仅含有无向边，这样的图称为无向图。不含多重边及环的图称为简单图。

设无向图G＝＜V，E＞，顶点v（vEV）关联的边数称作该顶点的度数，简称为度，记为deg（v）。图G＝＜V，E＞中，顶点度数总和等于边数的两倍，即

deg(v)=2|E|。

vEV

对图G中的顶点v，若deg（v）＝0，则v称为孤立点；若deg（v）＝1，则v称为悬挂点；若v有环，则计算度时使deg（v）增加2；若deg（v）为奇数，称v为奇顶点或奇点；若deg（v）为偶数，称v为偶顶点或偶点。

设G＝＜V，E＞是一个有向图，以顶点v为起点的有向边的个数称为v的出度，记为deg＋（v）；以顶点v为终点的有向边的个数称为v的入度，记为deg（v）。顶点的出度与人度之和就是该顶点的度数，即deg（v）＝deg＋（v）＋deg（v）。

设含n个顶点的简单无向图G＝＜V，E＞中，若每个顶点都与其余的n-1个顶点邻接，则称G为n阶（无向）完全图，记作Kn。n阶（无向）完全图中共有n(n-1)条边。

设G＝（V，E）是n阶无向简单图，以V为顶点集、所有属于Kn但不属于G的边为边集所构成的图，称为G相对于Kn的补图，简称为G的补图，记作G。

对于无向图G＝＜V，E＞，记


·26·

称Δ（G）为图G的最大度，称8（G）为图G的最小度。

设图G＝（V，E），如有图G＇＝（V＇，E＇＞，且ECE，V＇CV，则称G＇是G的子图。如果G的子图包含G的所有顶点，即E＇CE，V＇＝V，则G＇称为G的生成子图。

［单选、计算］图的同构。

图G1与图G2同构的充要条件是：图G1与图G2的顶点和边分别存在一一对应且保持关联关系。

8.2 图的连通性

给定图G＝＜V，E＞，G中顶点与边的交替序列r＝vi。ej，vieiz＊&quot;ej，。称为联结vio到v的通路，其中ej，是关联顶点v；1与v；，的边，即ej，＝（v11，v，），r＝1,2，.··，n，。和v，分别称作P的起点和终点，P中边的条数n称为通路的长度。当vi。＝v时，Γ称作回路。若P的所有边均不相同，则P称为简单通路。当简单通路的起点与终点相同时，Γ称为简单回路。若简单通路P的所有顶点不同（除起点和终点可能相同外），则厂称为初级通路或路径。若初级通路的起点与终点相同时，称为初级回路。

在无向图G中，顶点u和v之间若存在通路，则称顶点u和顶点v是连通的。若图G中任何两个不同顶点都是连通的，则称G为连通图，否则称G为不连通图。

在简单有向图G中，任何一对顶点间至少有一个顶点到另一个顶点是可达的，则称这个图是单侧连通的。如果对于图G中任何一对顶点，两者之间是相互可达，则称这个图是强连通的。如果在图G中，略去边的方向，将它看成无向图后，图是连通的，则该图称为弱连通的。

设无向图G＝（V，E》为连通图，对任意的顶点wEV，若删除w及与w相关联的所有边后，无向图不再连通，则w称为割点。

设无向图G＝＜V，E》为连通图，对任意的边eEE，若删除e后无向图不再连通，则e称为割边，也称为桥。

8.3 图的表示

［计算、综合应用］邻接矩阵。

对于简单图，邻接矩阵M可定义如下：

M[i][j]=

1，若（vi，vj）EE，1≤i，j≤n，

0，若（vi，vj）E，1≤i，j≤n。


第8章图

·27·


·28· 离散数学


设M是n个顶点的简单图G的邻接矩阵，M＝（m／））是M的k次幂，则在M中的（m／））等于顶点v；和v；之间长度为k的通路的数目。

［计算、综合应用］可达性矩阵。

设G是含n个顶点无多重边的图，定义n阶方阵P（G）＝（P；）为路径矩阵，其中

=d 1，若v；与v；之间至少存在一条通路，

0，若v；与v；不存在通路。

一般来讲，可由图G的邻接矩阵A得到可达性矩阵P，即设Bn＝A＋A2＋＋A＂，再从B，中仅将不为零的元素改换为1，由此得到可达性矩阵。

第9章图的应用

9.1 欧拉图与哈密顿图

在连通图G中，经过G中每条边一次且仅一次的通路，称为欧拉通路或欧拉路；若欧拉通路为回路，则称为欧拉回路。具有欧拉回路的图称为欧拉图，含有欧拉通路但没有欧拉回路的图称为半欧拉图。

无向连通图G是欧拉图的充分必要条件是G是连通的且无奇点。

无向图G具有一条欧拉通路的充分必要条件是G是连通的且恰有两个奇点。

给定无向图G，若存在一条路L，经过图中每个顶点一次且仅一次，则L称为哈密顿路，简称为H-路；若存在一条回路C，经过图中的每个顶点一次且仅一次，C称作哈密顿回路，简称为H-回路。具有哈密顿回路的图称作哈密顿图，简称为H-图。

设G是具有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n-1，则在G中存在一条哈密顿路。

设G是具有n个顶点的简单图，如果G中每一对顶点度数之和大于等于n，则在G中存在一条哈密顿回路。

9.2 平面图

设G是一个连通平面图，G的边将G所在的平面划分成若干个区域，每个区域称为G的一个面，其中面积无限的区域称为无限面或外部面。面积有限的区域称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面

第9章图的应用

·29· 的次数。若区域记为R，则次数可记为deg（R）。

［单选、计算］连通平面图的性质。

（1）设连通平面图G，面的次数之和等于其边数的两倍。

（2）设有一个连通平面图G，共有n个顶点和m条边，其平面表示中共有r个面，则n-m＋r＝2成立。此公式称为欧拉公式。

（3）设G是一个有v个顶点m条边的连通简单平面图，若v≥3，则m≤30-6。

9.3 树及其遍历

［单选、填空、计算］树的基本概念。

给定图T，有n个结点，则下列命题是等价的：

（1）T是树。

（2）T无回路，且T的任何两个顶点间有唯一一条路。

（3）T无回路，且有n-1条边。

（4）T是连通的，且有n-1条边。

（5）T是连通的，但删去任何一条边后便不再连通。

（6）T无回路，但增加任何一条边，将得到唯一的一个回路。

设无向连通带权图G＝＜V，E，W＞，T是G的一棵生成树，T的各边权值之和称为T的权，记作W（T）。G的所有生成树中权值最小的生成树称为最小生成树。

［计算、综合应用］求最小生成树的算法。

设图G＝＜V，E，W＞是无向连通带权图，它有m条边e1，e2，···，em，各边上的权依次为：a1，a2，＂，am，不妨设a1≤a2≤·．·≤am。

（1）初始准备：将图中的所有顶点加人到生成树T中，但不包含任何的边。此时T中仅含有顶点，这些顶点分别自成一个连通分量，连通分量的个数为m＝｜Vl。

（2）依次检查各边e1，e2，．．，em，对当前的边ei，如果e；所依附的两个顶点分别位于生成树的两个连通分量上，则将e；加入到生成树T中，并令e；所依附的两个顶点所在的两个连通分量合并成一个，生成树中连通分量的个数减1；如果e；依附的两个顶点已经位于同一个连通分量上，则舍弃ei，再看下一条边e＋1。当生成树T中含有｜VI-1条边时，过程结束。此时，原来的｜V｜个连通分量最终合并成一个。

树的结点具有&quot;层次&quot;性。设某结点v位于i层，则v的子结点位于i＋1

·30 离散数学

层。约定根位于0层。树中结点的最大层数定义为树的深度，最大层数加1为树的高度。

在有根树中，若每一个结点的出度小于等于m，则称这棵树为m叉树。如果每一个结点的出度恰好等于m或零，则称这棵树为完全m叉树。若完全m叉树的所有叶结点的层次相同，则称其为正则m叉树。

二叉树是指有序树中任何结点的子结点的个数不多于2个，即结点的出度或为0或为1或为2。位于左侧的子结点称为左子结点，位于右侧的子结点称为右子结点。以左子结点为根的子树称为左子树，以右子结点为根的子树称为右子树。二叉树的5种基本形态如下图所示。

a）空树 b）仅有根结点 c）右子树为空 d）左子树为空 e）左右子树俱全


图 二叉树的5种基本形态

设有完全m叉树T，其叶结点数为t，分支结点数为i，则（m-1）i＝t-1。